package com.s6.sort2;

import com.s6.sort1.ArrayUtils;

/**
 * 快速排序
 */
public class QuickSort {

	public static void main(String[] args) {
		int[] array = ArrayUtils.randomInt();
		ArrayUtils.print(array);
		sort(array);
		ArrayUtils.print(array);
	}

	public static void sort(int[] array) {
		sort(array, 0, array.length - 1);
	}

	public static void sort(int[] array, int start, int end) {
		if (start >= end) {
			return;
		}
		int pivot = partitionBetter(array, start, end);
		sort(array, start, pivot - 1);
		sort(array, pivot + 1, end);
	}

	// (非原地，不推荐)比较耗时的区分左右 1
	private static int partition(int[] array, int start, int end) {
		int pivotValue = array[end];
		int[] tempLeft = new int[end - start + 1];
		int[] tempRight = new int[end - start + 1];
		int i = 0, j = 0;
		int x;
		for (x = start; x < end; x++) {
			if (array[x] <= pivotValue) {
				tempLeft[i++] = array[x];
			} else {
				tempRight[j++] = array[x];
			}
		}

		for (x = 0; x < i; x++) {
			array[start + x] = tempLeft[x];
		}
		array[start + i] = pivotValue;
		for (x = 0; x < j; x++) {
			array[start + i + 1 + x] = tempRight[x];
		}
		return start + i;
	}

	// (推荐)原地比较 2
	private static int partitionBetter(int[] array, int start, int end) {
		int pivotValue = array[end];
		int i = start;
		for (int j = start; j < end; j++) {
			if (array[j] < pivotValue) {
				ArrayUtils.swap(array, i, j);
				i++;
			}
		}
		ArrayUtils.swap(array, i, end);
		return i;
	}

}
